package Leetcode第二期;

import java.util.*;

/**
 * @author : K k
 * @date : 10:07 2020/10/2
 * 给定一个不可包含重复数字的序列，返回所有不重复的全排列。
 *
 * 示例:
 *
 * 输入: [1,2,3] 输出：全排列
 */
public class 全排列_46 {
    List<List<Integer>> res=new ArrayList<>();
    Deque<Integer> path=new LinkedList<>();
    //访问位
    boolean[] visited;

    public List<List<Integer>> permute(int[] nums) {
        int n=nums.length;
        visited=new boolean[n];

        dfsSolver(nums,0,n);
        return res;
    }

    private void dfsSolver(int[] nums, int index, int len) {
        if (path.size()==len){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i=0;i<len;i++){
            if (visited[i]==false) {
                visited[i] = true;
                path.addLast(nums[i]);
                dfsSolver(nums, i,len);
                visited[i]=false;
                path.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        全排列_46 x=new 全排列_46();
        System.out.println(x.permute(new int[]{1, 2, 3}));
    }

}
